// https://www.lintcode.com/problem/missing-ranges/description
class Solution {
public:
    /*
     * @param nums: a sorted integer array
     * @param lower: An integer
     * @param upper: An integer
     * @return: a list of its missing ranges
     */
     
// 输入
// [2147483647]
// 0
// 2147483647
// MAX_INT: 2^31 - 1
// 期望答案
// ["0->2147483646"]

// 输入
// []
// 1
// 1
// 期望答案
// ["1"]

// 输入
// [-2147483648,-2147483648,0,2147483647,2147483647]
// -2147483648
// 2147483647
// 期望答案
// ["-2147483647->-1","1->2147483646"]
  
  
// - 快速实现简单问题，利用函数让代码更简洁
// - 特殊情况的处理(corner case):
// 1. 输入数组为空
// 2. 溢出：
// MAX_INT + 1 = - MAX_INT 溢出
// 法一：有加减的地方改成long，函数参数也改成long (64位整型，20多位数)
// 法二（个）：INT_MAX?不太好弄
// (python是弱类型的语言，自带高精度的加减乘除，不用担心)
    void addRange(vector<string> &ans, long st, long end)
    {
        if (st > end)
        {
            return;
        }
        else if (st == end)
        {
            ans.push_back(to_string(st));
        }
        else
        {
            ans.push_back(to_string(st) + "->" + to_string(end));
        }
    }
     
    vector<string> findMissingRanges(vector<int> &nums, int lower, int upper) {
        // write your code here
        vector<string> result;
        if (nums.size() == 0)
        {
            addRange(result, lower, upper);
            return result;
        }
        addRange(result, lower, (long)nums[0] - 1);
        for (int i = 1; i < nums.size(); i++)
        {
            addRange(result, (long)nums[i - 1] + 1, (long)nums[i] - 1);
        }
        addRange(result, (long)nums.back() + 1, upper);
        return result;
    }
};